/**
 * @description 堆排序
 * @example 升序
 * 1. 将待排序的数组构造成一个大顶堆（父节点>=左右子节点），整个堆的最大值在顶部
 * 2. 将数组首尾元素交换，末尾的将是最大值
 * 3. 重复1和2，重新构建一个堆，把最大值放在顶部，继续首尾元素交换
 * @example 降序，步骤和上面一样，只是在第一步将数组构建成小顶堆（父节点<=左右子节点）
 */
export default class Heap {
  public static asc(arr: number[] = []) {
    const length = arr.length;
    if (length < 1) {
      return;
    }
    this.buildBigHeap(arr);
    for (let l = length - 1; l > 0; l--) {
      const temp = arr[l];
      arr[l] = arr[0];
      arr[0] = temp;
      this.adjustheap(arr, 0, l);
    }
  }

  public static buildBigHeap(arr: number[]) {
    // 从最后一个非叶子节点开始，从左到右，从下到上进行遍历
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
      this.adjustheap(arr, i, arr.length);
    }
  }

  private static adjustheap(arr: number[], i: number, length: number) {
    let index = i;
    for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
      if (k + 1 < length && arr[k] < arr[k + 1]) {
        k++;
      }
      if (arr[k] > arr[index]) {
        const temp = arr[index];
        arr[index] = arr[k];
        arr[k] = temp;
        index = k;
      } else {
        break;
      }
    }
  }

  public static desc(arr: number[] = []) {
      const length = arr.length;
      if (length < 1) {
        return;
      }
      this.buildSmallHeap(arr);
      for (let l = length - 1; l > 0; l--) {
        const temp = arr[l];
        arr[l] = arr[0];
        arr[0] = temp;
        this.tsrHeap(arr, 0, l);
      }
  }

  public static buildSmallHeap(arr: number[]) {
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
      this.tsrHeap(arr, i, arr.length);
    }
  }

  private static tsrHeap(arr: number[], i: number, length: number) {
    let index = i;
    for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
      if (k + 1 < length && arr[k + 1] < arr[k]) {
        k++;
      }
      if (arr[k] < arr[index]) {
        const temp = arr[k];
        arr[k] = arr[index];
        arr[index] = temp;
        index = k;
      } else {
        break;
      }
    }
  }
}